package com.lry.basic.algorithm.recursion;

import java.util.*;

class IP {

    List<String> list = new ArrayList();

    public static void main(String[] args) {
        System.out.println(new IP().restoreIpAddresses("25525511135"));
    }

    public List<String> restoreIpAddresses(String s) {
        Stack<String> queue = new Stack<>();
        dfs(s,queue,0);
        return list;
    }

    private void dfs(String s,Stack<String> path, int index){
        int part = path.size();
        if(s.length()-index>(4-part)*3){
            return;
        }
        if(part==4&&index==s.length()){
            list.add(String.join(".", path));
            return;
        }
        for(int i=0;i<3;i++){
            //判断从index到index+i能否构成ip
            if(index+i>=s.length()){
                break;
            }
            int ip = judgeIfIpSegment(s,index,index+i);
            if(ip!=-1){
                path.push(""+ip);
                dfs(s,path,index+i+1);
                path.pop();
            }
        }

    }

     /**
     * 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
     * 判断的同时顺便把类型转了
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    private int judgeIfIpSegment(String s, int left, int right) {
        int len = right - left + 1;

        // 大于 1 位的时候，不能以 0 开头
        if (len > 1 && s.charAt(left) == '0') {
            return -1;
        }

        // 转成 int 类型
        int res = 0;
        for (int i = left; i <= right; i++) {
            res = res * 10 + s.charAt(i) - '0';
        }

        if (res > 255) {
            return -1;
        }
        return res;
    }

}
